package com.cet.qz.unit01.chapter1_3;

import edu.princeton.cs.algs4.StdRandom;

import java.util.Iterator;

/**
 * @program: algorithm
 * @description: 随机背包
 * @author: 陈恩涛
 * @create: 2021-04-21 22:05
 **/
public class RandomBag<Item> implements Iterable<Item> {


    private Item[] a = (Item[]) new Object[1];
    private int top = -1; //指向栈顶元素

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }

    public void add(Item item) {
        if (top == a.length - 1) {
            resize(2 * a.length);
        }
        a[++top] = item;
    }

    private void resize(int max) {
        Item[] items = (Item[]) new Object[max];
        for (int i = 0; i < a.length; i++) {
            items[i] = a[i];
        }
        a = items;
    }

    @Override
    public Iterator<Item> iterator() {
        return new BagIterator(a,top + 1);
    }

    class BagIterator implements Iterator<Item> {

        private Item[] items;
        private int top;

        public BagIterator(Item[] items,int n) {
            for (int i = 0; i < n; i++) {
                int r = i + StdRandom.uniform(n - i);
                Item temp = items[r];
                items[r] = items[i];
                items[i] = temp;
            }
            this.top = n - 1;
            this.items = items;
        }

        @Override
        public boolean hasNext() {
            return this.top != -1;
        }

        @Override
        public Item next() {
            return items[this.top--];
        }

        @Override
        public void remove() {

        }
    }

    public static void main(String[] args) {
        RandomBag<Integer> bag = new RandomBag<>();
        bag.add(1);
        bag.add(2);
        bag.add(3);
        bag.add(4);
        for (Integer integer : bag) {
            System.out.println(integer);
        }
    }

}
